package a00_LeetCode.LinkedList;

import a00_LeetCode.Tree.TreeNode;

/**
 * @Author quan
 * @Description 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。
 * 你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
 * @Date 2023/4/1 11:53
 */
public class Num24_swapPairs {
    /**
     * 迭代法
     */
   /* public ListNode swapPairs(ListNode head) {
        //模拟过程
        ListNode dummyHead  = new ListNode();
        dummyHead.next = head;
        //cur是被交换节点的前驱
        ListNode cur = dummyHead;
        while (cur.next!=null && cur.next.next!=null){
            //提前记录临时节点值，不然更改指向后，值就发生了变化
            ListNode temp1 = cur.next;
            ListNode temp2 =cur.next.next.next;
            cur.next = cur.next.next;
            cur.next.next = temp1;
            cur.next.next.next = temp2;
            //更新cur的位置，为下一轮交换做准备
            cur = cur.next.next;
        }
        return dummyHead.next;
    }*/

    /**
     * 递归法
     */
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        //先递归的反转后面的子链表
        ListNode node = head.next;
        //自己做的时候将44行代码写成了如下两行，就会报错。体会一下两者的区别到底在哪里？？？递归什么时候需要返回值接收呢？
        ListNode newNode = swapPairs(node.next);
//        ListNode newNode = node.next;
//        swapPairs(newNode);
        //再交换最开始剩下的头部链表
        node.next = head;
        //连接子链表和开始的头链表
        head.next = newNode;
        return node;
    }
}
